package com.codingvip.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author Tony.Han
 * @Created at 2020/4/10 11:13 下午
 * Desc:
 */
public class DoubleLink {

    public static void main(String[] args) {
        TreeNode node = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        node.left=node2;
        node.right=node3;
        node2.left = node4;
        node2.right = node5;
        node3.left=node6;
        node3.right = node7;
        DoubleLink doubleLink = new DoubleLink();
        TreeNode node1 = doubleLink.linkResult(node);
        System.out.println(node1);


    }

    TreeNode head,prev;
    public TreeNode  linkResult(TreeNode node){
        List<TreeNode> inorderList=new ArrayList();
        //得到中序列表
//        inorderVisit(node);
        inorderVisit2(node, inorderList);
//        //创建双向链表
        if(inorderList.size()==0){
            return null;
        }
        return  createDoubleList(inorderList);
    }
    public TreeNode createDoubleList(List<TreeNode> inorderList){
        TreeNode head=inorderList.get(0);
        TreeNode h=head;
        for(int i=1;i<inorderList.size();i++){
            TreeNode current=inorderList.get(i);
            current.left=h;
            h.right=current;
            h=current;
        }
        return head;
    }
    public void inorderVisit(TreeNode current){
        if(null==current){
            return;
        }

        inorderVisit(current.left);
        System.out.println(current.val);
        if (head== null) {
            prev = current;
            head=current;
        }else{
            current.left = prev;
            prev.right=current;
            prev=current;
        }
        inorderVisit(current.right);

    }
    public void inorderVisit2(TreeNode current,List<TreeNode> resultList){
        if(null==current){
            return;
        }

        inorderVisit2(current.left,resultList);
        resultList.add(current);

        System.out.println(current.val);
        inorderVisit2(current.right,resultList);

    }
}
